Inductive Relations
-------------------

CSF inductively defines relations via the IMSOS format.

These relations are binary, and may carry around additional
information via MSOS labels.

Rules are specified using the IMSOS notation.
There are these relations:
* Small step dynamic semantics -->
* Type inhabitance :
* Subtyping <
* Compile time resolution ==> (big step)
* Compile time type evaluation ~~> (big step)

The --> relation is used transitively to produce the runtime trace of
a program.

Subtyping < is automatically reflexive and transitive (one can think
of built-in rules).

The formula `term :< type' is short for `term : X , X < type' where X
is some fresh anonymous variable.

Rules follow Prolog's conventions, in that Capitalised identifiers
correspond to variables and lowercase ones to constants.

Rewriting
---------

In addition, systems defined in CSF also contain equational rewrites:
X = Y says that X should be simplified to Y in a context free
manner. This allows operations to be defined on data.

Signatures
----------

Each funcon (constructor) can have an associated (context-free)
signature. This can be used to check if a term is well-formed using
`deccheck'.

Signatures may be polymorphic, with X,Y,... ranging over arbitrary
sorts.

Side conditions may occur inside braces { - }. One example is val(X),
restricting the range of X to only val sorts (see below). Another
example is for use in higher order funcons (see below also).

Value Sorts
-----------

Some sorts are denoted as value (data) sorts. Inclusion of value sorts
can be checked implicitly at runtime based on variable names. For
example, if `boolean' is a value sort then

       foo(Boolean) --> ...

will only fire if the argument of foo is a Boolean.

The built in sort `val' denotes the union of all value sorts and
`ground' to terms X such that every subterm of X is a value.

Inductive data definitions are all value sorts.

Implicit Rules
--------------

The signature of a given funcon can automatically generate rules for
that funcon. For example, if the signature of a funcon f indicates
that it is binary and it's second argument is some val sort, a
`patience rule' in that argument will be generated:

     Y --> Y'
------------------
f(X,Y) --> f(X,Y')

Correspondingly, the signature of f(X,Y):Z will be lifted to
f(X,->Y):->Z. If S is a val sort, then ->S denotes a sort of
computations whose final states are in S.

This allows operations on vals to be lifted to operations on
computations where arguments are evaluated strictly.

We also generate rules automatically in the following ways:

* Resolution --- all funcons preserve the ==> relation providing no
  manual resolution rules are otherwise specified. If f is binary,
  then the rule
                X ==> X', Y ==> Y'
              ----------------------
              f(X,Y) ==> f(X',Y') is
  generated. Same applies to type evaluation ~~>.

* Typing --- typing rules for value sorts and data constructors

Translation Checking
--------------------

For translation time, an underapproximation of signature checking is
available. If X and Y are val sorts and X < Y, then an element of ->Y
will be permitted where an element of ->X is expected. In the tool
this is `supcheck'.

For example, if_true has lifted signature if_true(->bool,X,X) : X. In
Ocaml Light, bool is included in value, and so under this system any
expression (= ->value) can be included in the first position (=
->bool) as bool < value. This is needed as syntactic sorts in Ocaml do
not make the same distinctions as the funcon syntactic sorts.

Higher-order funcons
--------------------

Funcons may be higher order, e.g.

  Funcon abs F: abs { F(X) : value }

indicates that abs F is a funcon of sort 'abs', whenever F is a funcon
of sort F(X) : value, for some X.

MSOS labels
-----------

MSOS label components may be writeable, readable, or
changeable. Readable components may be denoted before the turn style
|-, writeable components inside the arrow, and changeable components
using tuple notation either side of the arrow. Unobservability and
composition are defined using the mechanics of MSOS, following the
`Relation:' declarations.
